#include <iostream>
#include <utility>
#include <cassert>

#define PRINT_INFO

namespace stl_self
{
    template <typename Type>
    struct list_node
    {
        list_node<Type> *_next;
        list_node<Type> *_prev;
        Type _value;
        explicit list_node(const Type &value = Type()) : _value(value), _next(nullptr), _prev(nullptr) {}
        ~list_node() = default;
    }; // struct List_node

    template <typename Type, typename Reference, typename Pointer>
    struct list_iterator
    {
        typedef list_node<Type> node;
        typedef list_iterator<Type, Reference, Pointer> self_type;
        typedef list_iterator<Type, Type &, Type *> iterator;
        typedef list_iterator<Type, const Type &, const Type *> const_iterator;
        node *_node;

        list_iterator(node *listNode) : _node(listNode) {}
        // iterator转换成const_iterator
        list_iterator(const iterator &other) : _node(other._node) {}
        ~list_iterator() = default;

        Reference operator*() { return _node->_value; }
        Pointer operator->() { return &_node->_value; }
        bool operator==(const self_type &self) { return _node == self._node; }
        bool operator!=(const self_type &self) { return !(*this == self); }

        self_type &operator++() // 前置++
        {
            _node = _node->_next;
            return *this;
        }

        self_type operator++(int) // 后置++
        {
            self_type buf(*this);
            _node = _node->_next;
            return buf;
        }

        self_type &operator--() // 前置--
        {
            _node = _node->_prev;
            return *this;
        }

        self_type operator--(int) // 后置--
        {
            self_type buf(*this);
            _node = _node->_prev;
            return buf;
        }

    }; // class list_iterator

    template <typename IteratorType, typename Reference, typename Pointer>
    struct list_reverse_iterator
    {
        typedef list_reverse_iterator<IteratorType, Reference, Pointer> self_type;
        IteratorType _current;

        list_reverse_iterator(IteratorType other) : _current(other) {}

        bool operator==(const self_type &other) { return _current == other._current; }
        bool operator!=(const self_type &other) { return _current != other._current; }
        Pointer operator->() { return &_current->_value; }

        Reference operator*()
        {
            IteratorType tmp = _current;
            --tmp;
            return *tmp;
        }

        self_type &operator++() // 前置++
        {
            --_current;
            return *this;
        }

        self_type operator++(int) // 后置++
        {
            self_type tmp = *this;
            --_current;
            return tmp;
        }

        self_type &operator--() // 前置--
        {
            ++_current;
            return *this;
        }

        self_type operator--(int) // 后置--
        {
            self_type tmp = *this;
            ++_current;
            return tmp;
        }

    }; // struct list_reverse_iterator

    template <typename Type>
    class list
    {
    private:
        typedef list_node<Type> node;

    public:
        typedef list_iterator<Type, Type &, Type *> iterator;
        typedef list_iterator<Type, const Type &, const Type *> const_iterator;

        typedef list_reverse_iterator<iterator, Type &, Type *> reverse_iterator;
        typedef list_reverse_iterator<iterator, const Type &, const Type *> const_reverse_iterator;

        iterator begin() { return iterator(_guard->_next); }
        iterator end() { return iterator(_guard); }
        const_iterator begin() const { return const_iterator(_guard->_next); }
        const_iterator end() const { return const_iterator(_guard); }

        reverse_iterator rbegin() { return reverse_iterator(end()); }
        reverse_iterator rend() { return reverse_iterator(begin()); }
        const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
        const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    private:
        node *_guard; // 哨兵位头结点

    private:
        void guard()
        {
            _guard = new node();
            _guard->_next = _guard;
            _guard->_prev = _guard;
        }

    public:
        explicit list()
        {
            guard();
#ifdef PRINT_INFO
            std::cout << "explicit list()" << std::endl;
#endif
        }

        explicit list(size_t n, const Type &value = Type())
        {
            guard();
            // while (n--)
            // {
            //     insert(begin(), value);
            // }
            insert(begin(), n, value);
#ifdef PRINT_INFO
            std::cout << "explicit list(size_t n, const Type &value = Type())" << std::endl;
#endif
        }

        list(const list<Type> &doubleList) // 拷贝构造
        {
            guard();
            insert(begin(), doubleList.begin(), doubleList.end());
#ifdef PRINT_INFO
            std::cout << " list(const list<Type> &doubleList)" << std::endl;
#endif
        }

        list(list<Type> &&doubleList)
        {
            swap(doubleList);
#ifdef PRINT_INFO
            std::cout << "list(list<Type> &&doubleList)" << std::endl;
#endif
        }

        ~list()
        {
            clear();
            delete _guard;
            _guard = nullptr;
#ifdef PRINT_INFO
            std::cout << "~list()" << std::endl;
#endif
        }

        list<Type> &operator=(const list<Type> &doubleList)
        {
            if (this != &doubleList)
            {
                guard();
                insert(begin(), doubleList.begin(), doubleList.end());
            }
#ifdef PRINT_INFO
            std::cout << "list<Type>& operator=(const list<Type>& doubleList)" << std::endl;
#endif
        }

        list<Type> &operator=(list<Type> &&doubleList)
        {
            if (this != &doubleList)
            {
                swap(doubleList);
            }
#ifdef PRINT_INFO
            std::cout << "list<Type>& operator=(list<Type>&& doubleList)" << std::endl;
#endif
        }

        iterator insert(const_iterator pos, const Type &value)
        {
            node *cur = pos._node;
            node *prev = pos._node->_prev;
            node *newNode = new node(value);
            prev->_next = newNode;
            newNode->_prev = prev;
            newNode->_next = cur;
            cur->_prev = newNode;
            return iterator(newNode);
        }

        iterator insert(const_iterator pos, size_t n, const Type &value)
        {
            while (n--)
            {
                insert(pos, value);
            }
        }

        template <typename InputIterator>
        iterator insert(const_iterator pos, InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                insert(pos, *first);
                ++first;
            }
        }

        iterator erase(const_iterator pos)
        {
            assert(pos != end());
            node *prev = pos._node->_prev;
            node *next = pos._node->_next;
            prev->_next = next;
            next->_prev = prev;
            delete pos._node;
            return iterator(next);
        }

        void push_back(const Type &value) { insert(end(), value); }
        void push_front(const Type &value) { insert(begin(), value); }
        void pop_back() { erase(--end()); }
        void pop_front() { erase(begin()); }
        Type &front() { return begin()._node->_value; }
        const Type &front() const { return begin()._node->_value; }
        Type &back() { return (--end())._node->_value; }
        const Type &back() const { return (--end())._node->_value; }
        void swap(list<Type> &doubleList) { std::swap(_guard, doubleList._guard); }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
        }

        void show() const
        {
            for (auto &x : *this)
            {
                std::cout << x << " ";
            }
            std::cout << std::endl;
        }
    };
} // namespace my_stl
